package com.vint.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * 最长连续数列，要求O(n)复杂度
 */
public class Leetcode128 {
    public static int longestConsecutive(int[] nums){
        if(null== nums||nums.length==0){
            return 0;
        }
        Map<Integer,Integer> indexMap = new HashMap<Integer, Integer>();
        Map<Integer,Boolean> visitMap = new HashMap<Integer, Boolean>();
        for(int i = 0; i < nums.length; i++){
            visitMap.put(i,false);
            if(!indexMap.containsKey(nums[i])){
                indexMap.put(nums[i],i);
            }
        }
        int max = 0;
        for(int i = 0; i < nums.length && !visitMap.get(i); i++){
            int length = 0;
            int sr = nums[i];
            int j = 0;
            //没有访问
            while (indexMap.containsKey(sr+j)&&!visitMap.get(indexMap.get(sr+j))){
               length++;
                //这里容易错
               visitMap.put(indexMap.get(sr+j),true);
                j++;
            }
            j = 1;
            while (indexMap.containsKey(sr-j)&&!visitMap.get(indexMap.get(sr-j))){
                length++;
                //这里容易错
                visitMap.put(indexMap.get(sr-j),true);
                j++;
            }
            if(length>max){
                max = length;
            }
        }
        return max;
    }
    public static void main(String[] args) {
        //int[] ex1 = {5,4,3,2,0,1};
        //int[] ex2 = {100,4,200,1,3,2};
        int[] ex3 = {-9,-4,9,-7,0,7,3,-1,6,2,-2,8,-2,0,2,-7,-5,-2,6,-5,0,-8,8,1,0,6,8,-8,-1};
        //int ret1 = longestConsecutive(ex1);
        //int ret2 = longestConsecutive(ex2);
        int ret3 = longestConsecutive(ex3);
        //System.out.println("success! " + ret3 + " " + ret2);

    }
}
